package LimitedTimeGame.Day_0215;

/**
 * @author zxc
 * @date 2023/02/15 11:45
 **/

import java.util.Stack;

/**
 * 题目 : 回文素数
 * 题目详述 ：
 * 求出大于或等于N的最小回文素数。
 * 回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。
 * 例如，2，3，5，7，11 以及13 是素数。
 * 回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。
 * 例如，12321 是回文数。
 *
 * 提示：
 * 1 <= N <= 10^8
 * 答案肯定存在，且小于 2 * 10^8。
 *
 */
public class PrimePalindrome {
    /**
     * 思路 ：
     * 即，获取大于等于N的回文数，判断其是否为素数;
     * 暴力法 ：很可能会超时。由于N的取值范围为[1 , 10^8]，所以N所能够取到的值是很大的;
     *
     * @param n
     * @return
     */
    public int primePalindrome(int n) {
        while(true){
            if(isPalindromes(n) && isPrime(n)){
                return n;
            }
            n++;
        }
    }
    // 判断该数是否为质数/素数
    private boolean isPrime(int n) {
        if(n == 1){
            return false;
        }
        for(int i = 2 ; i <= (int)Math.sqrt(n) ; i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
    // 判断该数是否为回文数
    private boolean isPalindromes(int n) {
        // 使用栈，来存储数字
        // 栈顶元素是数字的最高位;
        Stack<Integer> stack = new Stack<>();
        int temp = n;
        while(temp != 0){
            stack.push(temp % 10);
            temp /= 10;
        }
        // 弹栈 ：即，n % 10所获取的低位数字 与栈顶元素所代表的高位数字
        while(!stack.isEmpty()){
            if(n % 10 != stack.pop()){
                return false;
            }
            n = n / 10;
        }
        return true;
    }
}
